/*
题目链接：https://leetcode.cn/problems/count-the-number-of-good-nodes/description/
	刘沛民	2024-12-3
*/

class Solution {
public:
    int countGoodNodes(vector<vector<int>>& edges) {
        vector<vector<int>> dp(edges.size()+1);
        for(int i = 0;i<edges.size();i++){
            dp[edges[i][0]].push_back(edges[i][1]);
            dp[edges[i][1]].push_back(edges[i][0]);
        }
        int ans = 0;
        int n = dfs(-1,0,dp,ans);
        return edges.size()+1-ans;
    }

    int dfs(int i,int j,vector<vector<int>>& dp,int &ans){
        if(dp[j][0] == i && dp[j].size() == 1)
            return 1;
        int num = 1;
        int tmp_p = 0;
        int flag = 0;
        for(int k = 0;k<dp[j].size();k++){
            if(dp[j][k] != i){
                int tmp = dfs(j,dp[j][k],dp,ans);
                if(tmp != tmp_p && tmp_p != 0)
                    flag = 1;
                num += tmp;
                tmp_p = tmp;
            }
        }
        if(flag == 1)
            ans++;
        return num;
    }
};
